МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Звіт до лабораторної роботи №4 з курсу : “ Методи та засоби комп’ютерних інформаційних технологій ” на тему : “ Циклічні коди ” Варіант №20 Мета роботи - вивчення методiв завадостійкого кодування (циклічні коди) та особливостей їх програмної і апаратурної реалiзацiї. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ Побудова і застосування циклічних кодів. Коди називаються циклічними, якщо частина чи всі дозволені кодові комбінації для них можуть бути отримані шляхом циклічного зсуву однієї або кількох комбінацій. Циклічний зсув здійснюється справа наліво, причому крайній лівий символ переноситься в кінець комбінації. Циклічні коди відносяться до лінійних блочних кодів. Побудова циклічних кодів базується на використанні неприводимих у полі двійкового числа поліномів. Неприводимі поліноми діляться без остачі тільки на себе і на одиницю. Для отримання циклічного коду для заданої комбінації інформаційних бітів (наприклад, I(x)=x3+x2+1=1101) вона домножується на одночлен тієї ж степені (n=3), що і утворюючий поліном (K(x)=x3+x+1=1011). Це еквівалентно приписуванню n нулів справа у двійковому представлення коду (I(x)*xn=(x3+x2+1)*x3= x6+x5+x3=1101000). Значення коректуючих розрядів знаходимо в результаті ділення I(x)*x3 на K(x) I(x)*x3 / K(x)=x6+x5+x3/(x3+x+1)= x3+x2+x+1+1/(x3+x+1) бо у загальному випадку I(x)*xn/K(x)=Q(x)+R(x)/K(x) де: Q(x) - частка, а R(x) - остача. F(x)=Q(x)*K(x)=I(x)*xn+R(x) Для нашого прикладу F(x)=(x3+x2+x+1)*(x3+x+1)=(x3+x2+1)*x3+1 або F(x)=1111*1011=1101001=1101000+001 Це і буде кодова комбінація, яка визначалась. Причому, 1101 – інформаційна частина , а 001 – контрольна . Для знаходження і виправлення помилок в циклічних кодах отримані після передачі по каналу зв’язку комбінації діляться на утворюючий поліном для знаходження остачі. При діленні для бітів використовується не віднімання, а операція XOR. Циклічний зсув отриманої комбінації і ділення на утворюючий поліном здійснюють до тих пір поки кількість одиниць в остачі буде менша або рівна значенню коректуючої властивості коду (в нашому випадку виявляється і коректується одна помилка у коді). При цьому, якщо остача рівна нулю, то кодова комбінація правильна, а якщо не рівна нулю, то сума (по модулю 2) остачі з отриманою кодовою комбінацією дасть правильну кодову комбінацію. Утворюючий поліном відповідної степені вибирається з таблиць, приведених в літературі, на основі відомої довжини інформаційної частини коду. Наприклад для інформаційної частини довжиною чотири біти утворюючий поліном має степінь 3 і може приймати значення 1011 або 1101. Для позначення кодів використовується пара (j.k), де: j – загальна довжина коду, а k – довжина контрольної частини (наприклад (7.3)). Визначення і застосування циклічного надлишкового коду. Розглянуті циклічні коди забезпечують виявлення і корекцію помилок, однак це вимагає певних затрат (контрольна частина займає значну частину результуючого коду). В той же час при значній інтенсивності завад можливі багатократні і групові помилки для виявлення і виправлення яких потрібно збільшувати кількість контрольних розрядів та ускладнювати методи їх визначення. Тому у цьому випадку доцільно здійснювати тільки перевірку блоків переданої інформації і при наявності помилок не коректувати їх, а повторно передавати один або кілька блоків. Це може суттєво зменшити затрати часу. Варто зауважити, що при низькому рівні завад і відсутності помилок контрольна частина все одно передається, а при високому рівні завад контрольна частина не завжди забезпечує виявлення і корекцію помилок. Елементарним методом виявлення непарної кількості помилок у байті є контроль парності та непарності, тобто підрахунок кількості одиничних розрядів і доповнення її до парної чи непарної з виділенням одного додаткового розряду для збереження значення доповнення. Хоча цей метод не забезпечує виявлення парної кількості помилок він широко застосовується (наприклад у протоколі RS-232C). Для збіл...